解答1[Java]:
import java.util.Scanner;
public class Main {
public String multiply(String num1, String num2) {
int n1 = num1.length(), n2 = num2.length();
int[] products = new int[n1 + n2];
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int d1 = num1.charAt(i) - '0';
int d2 = num2.charAt(j) - '0';
products[i + j + 1] += d1 * d2;
}
}
int carry = 0;
for (int i = products.length - 1; i >= 0; i--) {
int tmp = (products[i] + carry) % 10;
carry = (products[i] + carry) / 10;
products[i] = tmp;
}
StringBuilder sb = new StringBuilder();
for (int num : products)
sb.append(num);
while (sb.length() != 0 && sb.charAt(0) == '0')
sb.deleteCharAt(0);
return sb.length() == 0 ? "0" : sb.toString();
}
}
这个算法基于一下规律:
- 位数分别为
i
和j
的两个数相乘,乘积的位数不超过i+j
位。 - 把结果看作一个大小为
i+j
的数组,那么第一个数的第i
位和第二个数的第j
位的乘积会影响结果的第i+j
位和第i+j+1
位。
因此,把第一个数的第 i
位和第二个数的第 j
位的乘积先存到结果的 i+j+1
位,最后再统一计算进位。